{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Шаблоны. Продвинутый материал"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Modern Template Techniques - Jon Kalb - Meeting C++ 2019](https://youtu.be/MLV4IVc4SwI)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Повторение основ"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Вопрос__: зачем нужны шаблоны?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Вопрос__: что может быть параметром шаблона?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Код для повторения:\n",
    "\n",
    "```c++\n",
    "template<typename T>\n",
    "void my_swap(T& x, T& y)\n",
    "{\n",
    "    T t = std::move(x);\n",
    "    x = std::move(y);\n",
    "    y = std::move(t);\n",
    "}\n",
    "\n",
    "template<>\n",
    "void my_swap<string>(string& x, string& y)\n",
    "{\n",
    "    x.swap(y);\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Шаблонный класс:\n",
    "    \n",
    "```c++\n",
    "template<typename T>\n",
    "struct Point3\n",
    "{\n",
    "    T x;\n",
    "    T y;\n",
    "    T z;\n",
    "};\n",
    "\n",
    "using Point3F = Point3<float>;\n",
    "using Point3D = Point3<double>;\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Или так:\n",
    "\n",
    "```c++\n",
    "template<typename T, int N>\n",
    "struct PointN\n",
    "{\n",
    "    T data[N];\n",
    "};\n",
    "\n",
    "using Point3F = PointN<float, 3>;\n",
    "using Point3D = PointN<double, 3>;\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Вопрос__: что такое частичная специализация? К чему её можно применять?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Вопрос__: скомпилируется ли этот код?\n",
    "    \n",
    "```c++\n",
    "template<typename T>\n",
    "class Person\n",
    "{\n",
    "private:\n",
    "    T id;\n",
    "    \n",
    "public:\n",
    "    void set_id(T i_id) { id = std::move(i_id); }\n",
    "    \n",
    "    const T& get_id() const { return id; }\n",
    "    \n",
    "    void clear_id() { id.clear(); }\n",
    "};\n",
    "\n",
    "int main()\n",
    "{\n",
    "    Person<int> p;\n",
    "    p.set_id(15);\n",
    "    std::cout << p.get_id() << std::endl;    \n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Вопрос__: как устроена компиляция и линковка шаблонов?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### SFINAE"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://en.cppreference.com/w/cpp/language/sfinae\n",
    "\n",
    "https://en.cppreference.com/w/cpp/language/overload_resolution\n",
    "\n",
    "https://jguegant.github.io/blogs/tech/sfinae-introduction.html\n",
    "\n",
    "https://www.bfilipek.com/2016/02/notes-on-c-sfinae.html"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Рассмотрим пример, как через SFINAE реализовать `my_swap` так, чтобы версия с методом была вызвана для всех типов, у которых есть соответствующий метод, а не только для тех, для которых не забыли сделать специализацию:\n",
    "\n",
    "```c++\n",
    "template<typename T>\n",
    "void my_swap(T& x, T& y)\n",
    "{\n",
    "    T t = std::move(x);\n",
    "    x = std::move(y);\n",
    "    y = std::move(t);\n",
    "}\n",
    "\n",
    "template<>\n",
    "void my_swap<string>(string& x, string& y)\n",
    "{\n",
    "    x.swap(y);\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "SFINAE = Substitution Failure Is Not An Error\n",
    "\n",
    "SFINAE - ovreloads resolution правило при наличии шаблонов: если не получается провести подстановку / сделать вывод шаблонных параметров, не генерировать ошибку компиляции, а продолжить искать другую подходящую перегрузку"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "void say_hello(int id) {\n",
    "    std::cout << \"int\"  << std::endl;\n",
    "}\n",
    "\n",
    "void say_hello(float id) {\n",
    "    std::cout << \"float\" << std::endl;\n",
    "}\n",
    "\n",
    "template<typename T>\n",
    "void say_hello(T t) {\n",
    "    std::cout << \"???\" << std::endl;\n",
    "}\n",
    "\n",
    "say_hello(5.f);\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Если речь идёт про SFINAE, то должны участвовать:\n",
    "* шаблоны\n",
    "* перегрузки\n",
    "* поиск нужной перегрузки"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Необходимые отступления:\n",
    "    \n",
    "* _substitution_ происходит в аргументах функции, возвращаемом типе и параметрах шаблона\n",
    "\n",
    "    ```c++\n",
    "    template<HERE>\n",
    "    HERE my_function(HERE x, HERE y)\n",
    "    { ...; }\n",
    "    ```\n",
    "\n",
    "* _substitution failure_ - ситуация, когда в результате подстановки в HERE получается ill-formed выражение\n",
    "    * если ill-formed случился не в местах подстановки, а, например, в теле функции после подстановки, то это не случай SFINAE, а обычный hard error\n",
    "    * если ill-formed случился как side-effect подстановки, то это тоже hard error (что считать side-effect-ом, что точно является sfinae error - подробнее читайте документацию): \n",
    "    \n",
    "```c++\n",
    "struct Point1 {\n",
    "    float x, y, z;\n",
    "};\n",
    "\n",
    "struct Point2 {\n",
    "    float x, y, z;        \n",
    "    using type = float;\n",
    "};\n",
    "\n",
    "\n",
    "// ex. 1\n",
    "template <class T, class = typename T::type>      // SFINAE failure if T has no member type\n",
    "void foo(T);\n",
    "\n",
    "// ex. 2\n",
    "template <typename T>\n",
    "struct B {\n",
    "    using type = typename T::type;\n",
    "};\n",
    "\n",
    "template <class T, class = typename T::type>      // SFINAE failure if T has no member type\n",
    "void foo(T);\n",
    "\n",
    "template <class T, class = typename B<T>::type>   // hard error if B<T> has no member type\n",
    "void foo (T);\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Демонстрация sfinae с cppreference (разобрать подробно):\n",
    "    \n",
    "```c++\n",
    "#include <iostream>\n",
    " \n",
    "// this overload is always in the set of overloads\n",
    "// ellipsis parameter has the lowest ranking for overload resolution\n",
    "void test(...)\n",
    "{\n",
    "    std::cout << \"test(...)\\n\";\n",
    "}\n",
    " \n",
    "// this overload is added to the set of overloads if\n",
    "// C is a reference-to-class type and F is a pointer to member function of C\n",
    "template <typename C, typename F>\n",
    "auto test(C c, F f) -> decltype((void)(c.*f)(), void())\n",
    "{\n",
    "    std::cout << \"test(object)\\n\";\n",
    "}\n",
    " \n",
    "// this overload is added to the set of overloads if\n",
    "// C is a pointer-to-class type and F is a pointer to member function of C\n",
    "template <typename C, typename F>\n",
    "auto test(C c, F f) -> decltype((void)(c->*f)(), void())\n",
    "{\n",
    "    std::cout << \"test(pointer)\\n\";\n",
    "}\n",
    " \n",
    "struct X { void f() {} };\n",
    " \n",
    "int main(){\n",
    "  X x;\n",
    "  test( x, &X::f);\n",
    "  test(&x, &X::f);\n",
    "  test(42, 1337);\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Стандартный трюк для определения какого-нибудь свойства типа (подробно и нудно разобрать каждую строчку и почему оно работает):\n",
    "\n",
    "```c++\n",
    "// trait helper:\n",
    "//     is_class<T>::value is true iff T is a class\n",
    "// \n",
    "//     is_class<int>::value == false\n",
    "//     is_class<string>::value == true\n",
    "template<typename T>\n",
    "class is_class {\n",
    "    typedef char yes[1];\n",
    "    typedef char no [2];\n",
    "    \n",
    "    template<typename C>\n",
    "    static yes& test(int C::*); // selected if C is a class type\n",
    "    \n",
    "    template<typename C>\n",
    "    static no&  test(...);      // selected otherwise\n",
    "    \n",
    "  public:\n",
    "    static bool const value = (sizeof(test<T>(nullptr)) == sizeof(yes));\n",
    "};\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Теперь мы можем написать идеальный `swap`.\n",
    "\n",
    "```c++\n",
    "template<typename T>\n",
    "class has_swap_method\n",
    "{\n",
    "    ...\n",
    "};\n",
    "\n",
    "...\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Шаг 1__: напишем `class has_swap_method` по аналогии с `class is_class`, который будет отвечать на вопрос, есть ли у шаблонного параметра метод `swap` (подробно объяснить)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "template<typename T>\n",
    "class has_swap_method\n",
    "{\n",
    "    typedef char yes[1];\n",
    "    typedef char no [2];\n",
    "    \n",
    "    template<typename U, void (U::*)(U&)>\n",
    "    class S {};\n",
    "    \n",
    "    template<typename U>\n",
    "    static yes& test(S<U, &U::swap>*);\n",
    "    \n",
    "    template<typename U>\n",
    "    static no&  test(...);\n",
    "\n",
    "public:\n",
    "    static constexpr bool value = sizeof(test<T>(nullptr)) == sizeof(yes);\n",
    "};\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Протестируем:\n",
    "\n",
    "```c++\n",
    "#include \"has_swap_method_trait.h\"\n",
    "\n",
    "#include <iostream>\n",
    "#include <string>\n",
    "#include <vector>\n",
    "\n",
    "template<typename T>\n",
    "void test_has_swap(const char* descr)\n",
    "{\n",
    "    std::cout << descr\n",
    "              << \" has swap method: \"\n",
    "              << has_swap_method<T>::value\n",
    "              << std::endl;\n",
    "}\n",
    "\n",
    "struct Point\n",
    "{\n",
    "    float x;\n",
    "    float y;\n",
    "};\n",
    "\n",
    "int main()\n",
    "{\n",
    "    test_has_swap<int>             (\"int             \");\n",
    "    test_has_swap<float>           (\"float           \");\n",
    "    test_has_swap<Point>           (\"Point           \");\n",
    "    test_has_swap<std::vector<int>>(\"std::vector<int>\");\n",
    "    test_has_swap<std::string>     (\"std::string     \");\n",
    "\n",
    "    return 0;\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Вывод:\n",
    "\n",
    "```sh\n",
    "int              has swap method: 0\n",
    "float            has swap method: 0\n",
    "Point            has swap method: 0\n",
    "std::vector<int> has swap method: 1\n",
    "std::string      has swap method: 1\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Шаг 2__: реализация `my_swap` (почти идеально):\n",
    "\n",
    "```c++\n",
    "template<typename T>\n",
    "void my_swap(T& x, T& y, std::false_type)\n",
    "{\n",
    "    std::cout << \"default swap\\n\";\n",
    "\n",
    "    T t = std::move(x);\n",
    "    x = std::move(y);\n",
    "    y = std::move(t);\n",
    "}\n",
    "\n",
    "template<typename T>\n",
    "void my_swap(T& x, T& y, std::true_type)\n",
    "{\n",
    "    std::cout << \"optimized swap\\n\";\n",
    "\n",
    "    x.swap(y);\n",
    "}\n",
    "\n",
    "template<typename T>\n",
    "void my_swap(T& x, T& y)\n",
    "{\n",
    "    my_swap(x, y,\n",
    "            std::integral_constant<bool, has_swap_method<T>::value>());\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Вопрос на понимание**: почему нельзя так?\n",
    "\n",
    "```c++\n",
    "template<typename T>\n",
    "void my_swap(T& x, T& y)\n",
    "{\n",
    "    if (has_swap_method<T>::value)\n",
    "    {\n",
    "        x.swap(y);\n",
    "    }\n",
    "    else\n",
    "    {\n",
    "        T t = std::move(x);\n",
    "        x = std::move(y);\n",
    "        y = std::move(t);\n",
    "    }\n",
    "}\n",
    "```\n",
    "\n",
    "**Замечание**: С С++17 есть `if constexpr` (показать на примере, как его написать, чтобы заработало)\n",
    "\n",
    "https://en.cppreference.com/w/cpp/language/if"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Протестируем:\n",
    "    \n",
    "```c++\n",
    "int main()\n",
    "{\n",
    "    std::cout << \"int:    \";\n",
    "    int i1 = 1, i2 = 2;\n",
    "    my_swap(i1, i2);\n",
    "\n",
    "    std::cout << \"string: \";\n",
    "    std::string s1 = \"abc\", s2 = \"def\";\n",
    "    my_swap(s1, s2);\n",
    "\n",
    "    return 0;\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Вывод:\n",
    "    \n",
    "```sh\n",
    "int:    default swap\n",
    "string: optimized swap\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Шаг 2__ через `std::enable_if` - лучше (объяснить):\n",
    "\n",
    "```c++\n",
    "// std::enable_if<compile-time-condition, some-type>::type\n",
    "//    * если compile-time-condition верно, то это some-type,\n",
    "//    * если compile-time-condition ложно, то это subsitution failure\n",
    "\n",
    "template<typename T>\n",
    "typename std::enable_if<has_swap_method<T>::value, void>::type\n",
    "my_swap(T& x, T& y)\n",
    "{\n",
    "    std::cout << \"optimized swap\\n\";\n",
    "    x.swap(y);\n",
    "}\n",
    "\n",
    "template<typename T>\n",
    "typename std::enable_if<!has_swap_method<T>::value, void>::type\n",
    "my_swap(T& x, T& y)\n",
    "{\n",
    "    std::cout << \"default swap\\n\";\n",
    "    T t = std::move(x);\n",
    "    x = std::move(y);\n",
    "    y = std::move(t);\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Протестируем:\n",
    "    \n",
    "```c++\n",
    "int main()\n",
    "{\n",
    "\n",
    "    std::cout << \"int:    \";\n",
    "    int i1 = 1, i2 = 2;\n",
    "    my_swap(i1, i2);\n",
    "\n",
    "    std::cout << \"string: \";\n",
    "    std::string s1 = \"abc\", s2 = \"def\";\n",
    "    my_swap(s1, s2);\n",
    "\n",
    "    return 0;\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Вывод:\n",
    "    \n",
    "```sh\n",
    "int:    default swap\n",
    "string: optimized swap\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Вопрос на понимание:__ почему такой вариант не скомпилируется?\n",
    "\n",
    "```c++\n",
    "template<typename T,\n",
    "         void (T::*)(T&) = &T::swap>\n",
    "void my_swap(T& x, T& y)\n",
    "{\n",
    "    std::cout << \"optimized swap\\n\";\n",
    "    x.swap(y);\n",
    "}\n",
    "\n",
    "template<typename T>\n",
    "void my_swap(T& x, T& y)\n",
    "{\n",
    "    std::cout << \"default swap\\n\";\n",
    "    T t = std::move(x);\n",
    "    x = std::move(y);\n",
    "    y = std::move(t);\n",
    "}\n",
    "\n",
    "int main()\n",
    "{\n",
    "\n",
    "    std::cout << \"int:    \";\n",
    "    int i1 = 1, i2 = 2;\n",
    "    my_swap(i1, i2);\n",
    "\n",
    "    std::cout << \"string: \";\n",
    "    std::string s1 = \"abc\", s2 = \"def\";\n",
    "    my_swap(s1, s2);\n",
    "\n",
    "    return 0;\n",
    "}\n",
    "```\n",
    "\n",
    "<details>\n",
    "<summary>ответ</summary>\n",
    "<p>\n",
    "    \n",
    "для `std::string` оба варианта перегрузки подходят и имеют одинаковый приоритет в механизме overloading resolution, поэтому компилятор не может сделать выбор и генерирует ошибку.\n",
    "\n",
    "</p>\n",
    "</details>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Альтернативный способ реализации `has_method_swap` с использованием `decltype`:\n",
    "\n",
    "```c++\n",
    "template<typename T>\n",
    "class has_swap_method\n",
    "{\n",
    "    template<typename U, void (U::*)(U&)>\n",
    "    class S {};\n",
    "\n",
    "    template <typename C>\n",
    "    static constexpr decltype(S<C, &C::swap>(), bool()) test(int /* unused */)\n",
    "    {\n",
    "        return true;\n",
    "    }\n",
    "\n",
    "    template <typename C>\n",
    "    static constexpr bool test(...)\n",
    "    {\n",
    "        return false;\n",
    "    }\n",
    "\n",
    "public:\n",
    "    static constexpr bool value = test<T>(int(0));\n",
    "};\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### variadic templates (C++11)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://en.cppreference.com/w/cpp/language/parameter_pack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*variadic templates* - фича стандарта С++11, позволяющая писать шаблоны с переменным числом аргументов.\n",
    "\n",
    "Начнём сразу с демонстрационного примера: шаблонная функция записывает строку в csv-файл\n",
    "\n",
    "```c++\n",
    "template<typename T>\n",
    "void printCSVLine(std::ostream& os, const T& v)\n",
    "{\n",
    "    os << v << std::endl;\n",
    "}\n",
    "\n",
    "template<typename T1, typename T2, typename ...Args>\n",
    "void printCSVLine(std::ostream& os, const T1& v1, const T2& v2, Args&&... args)\n",
    "{\n",
    "    os << v1 << ',';\n",
    "    printCSVLine(os, v2, args...);\n",
    "}\n",
    "```\n",
    "\n",
    "Использование:\n",
    "\n",
    "```c++\n",
    "printCSVLine(std::cout, \"name\",     \"surname\",   \"age\", \"gender\");\n",
    "printCSVLine(std::cout, \"Добрыня\",  \"Никитич\",   42,    'm');\n",
    "printCSVLine(std::cout, \"Илья\"s,    \"Муромец\"sv, 33,    'm');\n",
    "printCSVLine(std::cout, \"Василиса\", \"Премудрая\", 35,    'f');\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Пример форматированного вывода с cppreference:\n",
    "    \n",
    "```c++\n",
    "#include <iostream>\n",
    " \n",
    "void tprintf(const char* format) // base function\n",
    "{\n",
    "    std::cout << format;\n",
    "}\n",
    " \n",
    "template<typename T, typename... Targs>\n",
    "void tprintf(const char* format, const T& value, const Targs&... Fargs) // recursive variadic function\n",
    "{\n",
    "    for ( ; *format != '\\0'; format++ ) {\n",
    "        if ( *format == '%' ) {\n",
    "           std::cout << value;\n",
    "           tprintf(format + 1, Fargs...); // recursive call\n",
    "           return;\n",
    "        }\n",
    "        std::cout << *format;\n",
    "    }\n",
    "}\n",
    " \n",
    "int main()\n",
    "{\n",
    "    tprintf(\"% world% %\\n\",\"Hello\",'!',123);  // Hello world! 123\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Как работает `...`?\n",
    "\n",
    "Простое объяснение: выражение слева от `...` раскрывается для каждого аргумента. В зависимости от контекста между аргументами может быть автоматически поставлена запятая (надо смотреть правила).\n",
    "\n",
    "```c++\n",
    "f(&args...);             // f(&E1, &E2, &E3)\n",
    "f(n, ++args...);         // f(n, ++E1, ++E2, ++E3);\n",
    "f(++args..., n);         // f(++E1, ++E2, ++E3, n);\n",
    "f(h(args...) + args...); // f(h(E1,E2,E3) + E1, h(E1,E2,E3) + E2, h(E1,E2,E3) + E3)\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### fold expression (C++17)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://en.cppreference.com/w/cpp/language/fold"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*fold expressions* - фича стандарта С++17 - добавляет различные способы раскрытия `...` у variadic template."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Общий вид добавленных правил:\n",
    "    \n",
    "```c++\n",
    "( pack op ... )\n",
    "( ... op pack )\n",
    "( pack op ... op init )\n",
    "( init op ... op pack )\n",
    "```\n",
    "\n",
    "где op - бинарная/унарная правая/левая операция.\n",
    "\n",
    "Соответственно, 4 правила развёртки:\n",
    "\n",
    "* Unary right fold $(E op ...) ->  (E_1 op (... op (E_{N-1} op E_N)))$\n",
    "* Unary left fold $(... op E) -> (((E_1 op E_2) op ...) op E_N)$\n",
    "* Binary right fold $(E op ... op I) -> (E_1 op (... op (E_{N−1} op (E_N op I))))$\n",
    "* Binary left fold $(I op ... op E) -> ((((I op E_1) op E_2) op ...) op E_N)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Примеры их применения:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "template<typename T, typename ...Args>\n",
    "auto sum(const T& v, const Args&... args) {\n",
    "    return v + ... + args;\n",
    "}\n",
    "\n",
    "sum(1, 2, 3, 4, 5, 6, 7);  // 28\n",
    "sum(\"abc\"s, \"def\", \"ghi\");  // ?\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "template<typename ...Args>\n",
    "void printer(Args&&... args) {\n",
    "    (std::cout << ... << args) << '\\n';\n",
    "}\n",
    "\n",
    "printer(\"hello\", \"world\");  // helloworld\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### sizeof...(args) (C++11)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Есть особый оператор `sizeof...(args)`, который возвращает число аргументов.\n",
    "\n",
    "Рассмотрим его на примере добавления нескольких элементов в `std::vector`:\n",
    "\n",
    "```c++\n",
    "template<typename T, typename... Args>\n",
    "void add_to_vector(std::vector<T>& v, Args&&... args)\n",
    "{\n",
    "    v.reserve(v.size() + sizeof...(args));\n",
    "    (v.push_back(std::forward<Args>(args)), ...);\n",
    "}\n",
    "\n",
    "// usage:\n",
    "std::vector<std::string> v;\n",
    "add_to_vector(v, \"Добрыня\", \"Илюша\"s, \"Алёша\"sv);\n",
    "add_to_vector(v, \"Василиса\", \"Настасья\"s);\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Замечание**: почти все примеры на variadic templates были ученическими, но они являют собой достаточно мощный механизм.\n",
    "\n",
    "Классический пример \"боевого\" применения - форматирование строк `std::format`, варианты inplace конструирования `make_unique`/`make_shared`/`vector::emplace`/`optional::emplace` и т.д:\n",
    "\n",
    "```c++\n",
    "auto x = std::make_unique<std::vector<std::string>>(\"abc\", 10); \n",
    "```\n",
    "\n",
    "> template< class T, class... Args >\n",
    "  unique_ptr<T> make_unique( Args&&... args );\n",
    "\n",
    "```c++\n",
    "std::vector<std::string> v;\n",
    "v.emplace_back(\"a\", 10);\n",
    "```\n",
    "\n",
    "> template< class... Args >\n",
    "  reference emplace_back( Args&&... args );\n",
    "\n",
    "**Вопрос**: что такое и почему && ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### tag dispatching && type traits"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*tag dispatching* - техника выбора поведения/реализации, основыванная на типе одного из параметров (тэге) и механизме перегрузки. Обычно, этот параметр - пустая структурка."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "С примером простенького tag dispatching мы уже познакомились на примере `my_swap`:\n",
    "\n",
    "```c++\n",
    "template<typename T>\n",
    "void my_swap_dispatched(T& x, T& y, std::false_type)\n",
    "{\n",
    "    T t = std::move(x);\n",
    "    x = std::move(y);\n",
    "    y = std::move(t);\n",
    "}\n",
    "\n",
    "template<typename T>\n",
    "void my_swap_dispatched(T& x, T& y, std::true_type)\n",
    "{\n",
    "    x.swap(y);\n",
    "}\n",
    "\n",
    "template<typename T>\n",
    "void my_swap(T& x, T& y)\n",
    "{\n",
    "    my_swap_dispatched(x, y, std::integral_constant<bool, has_swap_method<T>::value>());\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Традииционный пример использования tag dispatching вместе с type triants: `std::advance`\n",
    "\n",
    "Что такое `std::advance`:\n",
    "\n",
    "```c++\n",
    "// интерфейс\n",
    "template< class InputIt, class Distance >\n",
    "void advance( InputIt& it, Distance n );\n",
    "\n",
    "// использование:\n",
    "std::vector<int> v = { ... };\n",
    "auto vit = v.begin();\n",
    "std::advance(vit, 5);  // один \"прыжок\"\n",
    "\n",
    "std::list<int> l = { ... };\n",
    "auto lit = l.end();\n",
    "std::advance(lit, -5);  // 5 \"прыжков\" назад\n",
    "\n",
    "std::forward_list<int> f = { ... };\n",
    "auto fit = f.begin();\n",
    "std::advance(fit, 5);  // 5 \"прыжков\" вперёд\n",
    "```\n",
    "\n",
    "Как его можно реализовать:\n",
    "\n",
    "```c++\n",
    "namespace std {\n",
    "  namespace detail {\n",
    "    template <class It, class D>\n",
    "    void advance_dispatch(It& i, D n, input_iterator_tag) {\n",
    "      while (n--) ++i;\n",
    "    }\n",
    "\n",
    "    template <class It, class D>\n",
    "    void advance_dispatch(It& i, D n, bidirectional_iterator_tag) {\n",
    "      if (n >= 0)\n",
    "        while (n--) ++i;\n",
    "      else\n",
    "        while (n++) --i;\n",
    "    }\n",
    "\n",
    "    template <class It, class D>\n",
    "    void advance_dispatch(It& i, D n, random_access_iterator_tag) {\n",
    "      i += n;\n",
    "    }\n",
    "  }\n",
    "\n",
    "  template <class It, class Distance>\n",
    "  void advance(It& i, Distance n) {\n",
    "    typename iterator_traits<It>::iterator_category category;\n",
    "    detail::advance_dispatch(i, n, category());\n",
    "  }\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Нюанс в определении типа `iterator_traits<It>::iterator_category`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Делается это примерно так:\n",
    "    \n",
    "```c++\n",
    "struct input_iterator_tag { };\n",
    "struct bidirectional_iterator_tag { };\n",
    "struct random_access_iterator_tag { };\n",
    "\n",
    "template<typename It>\n",
    "struct iterator_traits\n",
    "{\n",
    "    using iterator_category = input_iterator_tag;\n",
    "    ...\n",
    "};\n",
    "\n",
    "template<typename T>\n",
    "struct iterator_traits<std::vector<T>::iterator>\n",
    "{\n",
    "    using iterator_category = random_access_iterator_tag;\n",
    "    ...    \n",
    "};\n",
    "```\n",
    "\n",
    "После того как определён type trait для итераторов, любой алгоритм, желающий использовать преимущества random_access_iterator, может сделать это через tag dispatching.\n",
    "\n",
    "Минус подхода в том, что для такой реализации нужно для каждого итераторане забыть прописать iterator_traits (или он свалится в самый слабый вариант traits)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### стандартные type traits"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://en.cppreference.com/w/cpp/types\n",
    "\n",
    "В стандартную библиотеку добавлено большое кол-во trait-ов, чтобы программисты не мучились и не писали свои велосипеды. Полный список смотрите по ссылке, а вот некоторые из них:\n",
    "\n",
    "```c++\n",
    "std::is_integral<T>\n",
    "std::is_floating_point<T>\n",
    "std::is_array<T>\n",
    "std::is_trivial<T>\n",
    "std::is_same<T, U>\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### deduction guides (C++17)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://en.cppreference.com/w/cpp/language/class_template_argument_deduction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*class template argument deduction* - нововведение С++17: при использовании шаблона класса программист не обязан указывать параметры шаблона, если компилятор может вывести их из контекста (и программиста устроит то, что вывел компилятор).\n",
    "\n",
    "```c++\n",
    "std::vector v = {1, 2, 3, 4, 5};    // std::vector<int> автоматически\n",
    "std::pair p = {42, 3.14};           // std::pair<int, double> автоматически\n",
    "std::list l = {\"hello\", \"world\" };  // ?\n",
    "```\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Именно поэтому работают примеры из лекции по многопотоности:\n",
    "    \n",
    "```c++\n",
    "std::mutex mtx;\n",
    "std::lock_guard guard(mtx);  // std::lock_guard<std::mutex> guard(mtx);\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Рассмотрим снова пример\n",
    "\n",
    "```c++\n",
    "std::vector v = {1, 2, 3, 4, 5};\n",
    "```\n",
    "\n",
    "Правило, по которому компилятор понимает, что при создании `std::vector<T>` из `std::initializer_list<int>` нужно взять `T = int`, называется *deduction guides*."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Какие-то правила прописаны по умолчанию и неявно применяются для всех классов (implicitly-generated deduction guides), какие они - читайте стандарт по ссылке."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Иногда неявных правил не хватает, и программисту хочется добавить свои. Такие правила называются пользовательскими (user defined deduction guides)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Для имеющихся контейнеров уже всё готово, поэтому предположим, у нас есть свой личный контейнер:\n",
    "    \n",
    "```c++\n",
    "template<typename T>\n",
    "class flat_set\n",
    "{\n",
    "public:\n",
    "    flat_set(std::initializer_list<T> items);\n",
    "    \n",
    "    template<typename It>\n",
    "    flat_set(It begin, It end);\n",
    "};\n",
    "```\n",
    "\n",
    "Напишем deduction guides для нашего типа:\n",
    "    \n",
    "```c++\n",
    "template<class It>\n",
    "flat_set(It begin, It end) -> flat_set<typename std::iterator_traits<It>::value_type>;\n",
    "```\n",
    "\n",
    "Использование:\n",
    "\n",
    "```c++\n",
    "flat_set x = {1, 2, 3, 4, 5}; // flat_set<int> по неявным правилам вывода\n",
    "\n",
    "std::vector v = {1, 2, 3, 4, 5};\n",
    "flat_set x{v.begin(), v.end()};  // flat_set<int> по нашему правилу\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Резюме**:\n",
    "\n",
    "* `SFINAE` - техника выбора более оптимизированной реализации на этапе компиляции по типу, пример с `my_swap` (шаблоны + перегрузки)\n",
    "* variadic templates && fold expressions - шаблоны переменного числа аргументов, необходимый механизм для функций `make_unique`, `make_shared`, `emplace_back`.\n",
    "* deduction guides - способ автоматического вывода типов у шаблонов классов через выражение справа."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Замечания после лекции:**\n",
    "* понять, действительно ли нужна запятая в decltype\n",
    "* попробовать упростить примеры"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
